Pascal's Triangle II

LeetCode 119 | Difficulty: Easy

Easy

Problem Description

Given an integer rowIndex, return the rowIndex^th (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

- `0 <= rowIndex <= 33`

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 204 ms)

Metric	Value
Runtime	204 ms
Memory	24.9 MB
Date	2019-12-15

Solution

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        int[] A = new int[rowIndex+1];
    A[0] = 1;
    for (int i = 1; i <= rowIndex; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            A[j] += A[j-1];
        }
    }
    
    return A.ToList();
    }
}

📜 2 more C# submission(s)

Submission (2020-02-21) — 208 ms, 25.4 MB

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        int[] A = new int[rowIndex+1];
    A[0] = 1;
    for (int i = 1; i <= rowIndex; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            A[j] += A[j-1];
        }
    }
    
    return A.ToList();
    }
}

Submission (2017-11-11) — 445 ms, N/A

public class Solution {
    public IList<int> GetRow(int rowIndex) {
    IList<IList<int>> rows = new List<IList<int>>();
    rows.Add(new List<int>() { 1 });
    for (int i = 1; i <= rowIndex; i++)
    {
        var row = new int[i + 1];
        row[0] = 1;
        row[i] = 1;
        for (int j = 1; j < i; j++)
        {
            row[j] = rows[i - 1][j - 1] + rows[i - 1][j];
        }
        rows.Add(row);
    }
    return rows[rowIndex];
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.